CRC, Cyclic Redundancy Check, 循环冗余校验

CRC的本质是除法，把待检验的数据当作一个很大（很长）的被除数，两边选定一个除数（有的文献叫poly），最后得到的余数就是CRC的校验值。

判定方法：

将消息和校验和分开。计算消息的校验和（在附加W个零后），并比较两个校验和。

把校验值放到数据的结尾，对整批进行校验和（不附加零），看看结果是否为零！

比较常见的是累加和校验，但是有以下缺点：

80 与 80 00 .. 00的计算结果一致，即如果数据里参杂了00是检测不出来的，对于不定长的检测不友好

因为是累加和，所以80 00有非常多的组合是校验值相等的，比如70 10, 79 06 等等

那么什么情况下会导致CRC失败呢？

CRC算术中的两个数字相加与普通二进制算术中的数字相加相同，除了没有进位。

无进位的加法及减法其实是异或运算（异或，不一样就或在一起：不一样为1，相同为0）

这意味着每对对应的比特确定对应的输出比特，而不参考任何其他比特位置。例如

加法的4中情况：

减法也是类似的：

with

这么一来，我们相当于把加法和减法合并成为了一种算法，或者可以理解为加法和减法这里称为了一种互逆运算，比如我们可以通过加减相同的数量，可以从1010到1001：

所以在无进位的加减法里，1010不再可以被视为大于1001；

这么做有什么好处？

你会发现无论多长的数据bit在运算时都不再依赖于前一位或者后一位的状态，这和带进位的加法及带借位的减法不同，你可以理解为运行并行计算：

带进位的加法，高位的计算结果需要累加低位结果产生的进位，这就导致了必须要先计算低位，之后才能计算高位；比如下面的例子，如果带进位的话就必须从最右边开始计算，依次算到最左边得到结果。但是如果我们把进位取消，就会发现我从那边开始算都可以，当然也可以多位同时一起算（并行计算）

减法也是如此，不再赘述。

定义了加法后，我们可以进行乘法和除法。乘法是简单的，只不过在加法运算的时候使用XOR就行了

除法也是类似的，只不过有两点需要注意：

当除数和被除数的最高位都是1的时候，就当作是对齐了，就可以开始XOR运算，不要比较数据大小，比如 1001可以被1011除，至于商的结果是1或者0，没有人去关注，自己开心就好，因为这个算法压根就不用；

被除数和除数做减法时，需要使用无进位的减法，即XOR运算；

即使我们知道CRC的算法是基于除法，我们也不能直接使用除法运算，一个是待校验的数据很长，我们没有这么大的寄存器；再则，你知道除法在MCU中是怎么实现的吗？

现在我们假设一个消息数据为1101011011，选取除数为10011，使用CRC算法将消息除以poly：

除数poly的左边的高位的作用其实是给人看的（实际上参与运算的是0011），目的是干掉当前最高位的被除数，本质上是让poly和被除数对齐，然后开始XOR运算。

那么什么情况算是对齐呢？ 从例子上看，当被除数和除数的最高位都是1时，就算是对齐了。

转换成算法的思路就是，你也可以理解成一长串的数据不断的从右边移位到寄存器中，当寄存器最左边溢出的数值是1的时候，那么当前寄存器的数据就可以和poly异或运算了，用算法表示，大概是这样：